package com.zh.oauth.util;

/**
 * code is far away from bug with the animal protecting
 * ┏┓　　　┏┓
 * ┏┛┻━━━┛┻┓
 * ┃　　　　　　　┃
 * ┃　　　━　　　┃
 * ┃　┳┛　┗┳　┃
 * ┃　　　　　　　┃
 * ┃　　　┻　　　┃
 * ┃　　　　　　　┃
 * ┗━┓　　　┏━┛
 * 　　┃　　　┃神兽保佑
 * 　　┃　　　┃代码无BUG！
 * 　　┃　　　┗━━━┓
 * 　　┃　　　　　　　┣┓
 * 　　┃　　　　　　　┏┛
 * 　　┗┓┓┏━┳┓┏┛
 * 　　　┃┫┫　┃┫┫
 * 　　　┗┻┛　┗┻┛
 *
 * @Description: 排序工具
 * @Author: Li.HuiNeng
 * @Create in: 2019-09-16 18:01
 * @Version: 1.0.1
 */
public class SortUtil {

        public static final String SORT_TYPE_DESC = "desc";
        public static final String SORT_TYPE_ASC = "asc";

        /**
         * 交换数组中指定的两元素的位置
         *
         * @param source
         * @param x
         * @param y
         */
        private static void swap(int[] source, int x, int y) {
            int temp = source[x];
            source[x] = source[y];
            source[y] = temp;
        }

        /**
         * 冒泡排序----交换排序的一种
         * 方法：相邻两元素进行比较，如有需要则进行交换，每完成一次循环就将最大元素排在最后（如从小到大排序），下一次循环是将其他的数进行类似操作。
         * 性能：比较次数O(n^2),n^2/2；交换次数O(n^2),n^2/4
         *
         * @param source
         *            要排序的数组
         * @param sortType
         *            排序类型
         * @return
         */
        public static void bubbleSort(int[] source, String sortType) {
            if (sortType.equals("asc")) { // 正排序，从小排到大
                for (int i = source.length - 1; i > 0; i--) {
                    for (int j = 0; j < i; j++) {
                        if (source[j] > source[j + 1]) {
                            swap(source, j, j + 1);
                        }
                    }
                }
            } else if (sortType.equals("desc")) { // 倒排序，从大排到小
                for (int i = source.length - 1; i > 0; i--) {
                    for (int j = 0; j < i; j++) {
                        if (source[j] < source[j + 1]) {
                            swap(source, j, j + 1);
                        }
                    }
                }
            } else {
                System.out.println("您输入的排序类型错误！");
            }
        }

        /**
         * 直接选择排序法----选择排序的一种 方法：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，
         * 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 性能：比较次数O(n^2),n^2/2 交换次数O(n),n
         * 交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CUP时间多，所以选择排序比冒泡排序快。
         * 但是N比较大时，比较所需的CPU时间占主要地位，所以这时的性能和冒泡排序差不太多，但毫无疑问肯定要快些。
         *
         * @param source
         *            要排序的数组
         * @param sortType
         *            排序类型
         * @return
         */
        public static void selectSort(int[] source, String sortType) {

            if (sortType.equals("asc")) { // 正排序，从小排到大
                for (int i = 0; i < source.length; i++) {
                    for (int j = i + 1; j < source.length; j++) {
                        if (source[i] > source[j]) {
                            swap(source, i, j);
                        }
                    }
                }
            } else if (sortType.equals("desc")) { // 倒排序，从大排到小
                for (int i = 0; i < source.length; i++) {
                    for (int j = i + 1; j < source.length; j++) {
                        if (source[i] < source[j]) {
                            swap(source, i, j);
                        }
                    }
                }
            } else {
                System.out.println("您输入的排序类型错误！");
            }
        }

        /**
         * 插入排序 方法：将一个记录插入到已排好序的有序表（有可能是空表）中,从而得到一个新的记录数增1的有序表。 性能：比较次数O(n^2),n^2/4
         * 复制次数O(n),n^2/4 比较次数是前两者的一般，而复制所需的CPU时间较交换少，所以性能上比冒泡排序提高一倍多，而比选择排序也要快。
         *
         * @param source
         *            要排序的数组
         * @param sortType
         *            排序类型
         */
        public static void insertSort(int[] source, String sortType) {
            if (sortType.equals("asc")) { // 正排序，从小排到大
                for (int i = 1; i < source.length; i++) {
                    for (int j = i; (j > 0) && (source[j] < source[j - 1]); j--) {
                        swap(source, j, j - 1);
                    }
                }
            } else if (sortType.equals("desc")) { // 倒排序，从大排到小
                for (int i = 1; i < source.length; i++) {
                    for (int j = i; (j > 0) && (source[j] > source[j - 1]); j--) {
                        swap(source, j, j - 1);
                    }
                }
            } else {
                System.out.println("您输入的排序类型错误！");
            }
        }

        /**
         * 反转数组的方法
         *
         * @param source
         *            源数组
         */
        public static void reverse(int[] source) {

            int length = source.length;
            int temp = 0;// 临时变量

            for (int i = 0; i < length / 2; i++) {
                temp = source[i];
                source[i] = source[length - 1 - i];
                source[length - 1 - i] = temp;
            }
        }

        /**
         * 快速排序 快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。 步骤为：
         * 1. 从数列中挑出一个元素，称为 "基准"（pivot）， 2.
         * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面
         * （相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。 3.
         * 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
         * 递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了
         * 。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
         *
         * @param source
         *            待排序的数组
         * @param low
         * @param high
         * @see SortTest#qsort(int[], int, int)
         * @see SortTest#qsort_desc(int[], int, int)
         */
        public static void quickSort(int[] source, String sortType) {
            if (sortType.equals("asc")) { // 正排序，从小排到大
                qsort_asc(source, 0, source.length - 1);
            } else if (sortType.equals("desc")) { // 倒排序，从大排到小
                qsort_desc(source, 0, source.length - 1);
            } else {
                System.out.println("您输入的排序类型错误！");
            }
        }

        /**
         * 快速排序的具体实现，排正序
         *
         * @param source
         * @param low
         * @param high
         */
        private static void qsort_asc(int source[], int low, int high) {
            int i, j, x;
            if (low < high) { // 这个条件用来结束递归
                i = low;
                j = high;
                x = source[i];
                while (i < j) {
                    while (i < j && source[j] > x) {
                        j--; // 从右向左找第一个小于x的数
                    }
                    if (i < j) {
                        source[i] = source[j];
                        i++;
                    }
                    while (i < j && source[i] < x) {
                        i++; // 从左向右找第一个大于x的数
                    }
                    if (i < j) {
                        source[j] = source[i];
                        j--;
                    }
                }
                source[i] = x;
                qsort_asc(source, low, i - 1);
                qsort_asc(source, i + 1, high);
            }
        }

        /**
         * 快速排序的具体实现，排倒序
         *
         * @param source
         * @param low
         * @param high
         */
        private static void qsort_desc(int source[], int low, int high) {
            int i, j, x;
            if (low < high) { // 这个条件用来结束递归
                i = low;
                j = high;
                x = source[i];
                while (i < j) {
                    while (i < j && source[j] < x) {
                        j--; // 从右向左找第一个小于x的数
                    }
                    if (i < j) {
                        source[i] = source[j];
                        i++;
                    }
                    while (i < j && source[i] > x) {
                        i++; // 从左向右找第一个大于x的数
                    }
                    if (i < j) {
                        source[j] = source[i];
                        j--;
                    }
                }
                source[i] = x;
                qsort_desc(source, low, i - 1);
                qsort_desc(source, i + 1, high);
            }
        }

        /**
         * 二分法查找 查找线性表必须是有序列表
         *
         * @param source
         * @param key
         * @return
         */
        public static int binarySearch(int[] source, int key) {
            int low = 0, high = source.length - 1, mid;
            while (low <= high) {
                mid = (low + high) >>> 1; // 相当于mid = (low + high) / 2，但是效率会高些
                if (key == source[mid]) {
                    return mid;
                } else if (key < source[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            return -1;
        }

       /* public static void main(String[] args) {
            Sort sort = new Sort();
            int[] t = new int[] { 6, 3, 0, 6, 2, 8 };
            sort.bubbleSort(t, Sort.SORT_TYPE_DESC);
            System.out.println(Arrays.toString(t));
            // Sort sortTest = new Sort();
            //
            // int[] array = sortTest.createArray();
            //
            // System.out.println("==========冒泡排序后(正序)==========");
            // sortTest.bubbleSort(array, "asc");
            // System.out.println("==========冒泡排序后(倒序)==========");
            // sortTest.bubbleSort(array, "desc");
            //
            // array = sortTest.createArray();
            //
            // System.out.println("==========倒转数组后==========");
            // sortTest.reverse(array);
            //
            // array = sortTest.createArray();
            //
            // System.out.println("==========选择排序后(正序)==========");
            // sortTest.selectSort(array, "asc");
            // System.out.println("==========选择排序后(倒序)==========");
            // sortTest.selectSort(array, "desc");
            //
            // array = sortTest.createArray();
            //
            // System.out.println("==========插入排序后(正序)==========");
            // sortTest.insertSort(array, "asc");
            // System.out.println("==========插入排序后(倒序)==========");
            // sortTest.insertSort(array, "desc");
            //
            // array = sortTest.createArray();
            // System.out.println("==========快速排序后(正序)==========");
            // sortTest.quickSort(array, "asc");
            // sortTest.printArray(array);
            // System.out.println("==========快速排序后(倒序)==========");
            // sortTest.quickSort(array, "desc");
            // sortTest.printArray(array);
            //
            // System.out.println("==========数组二分查找==========");
            // System.out.println("您要找的数在第" + sortTest.binarySearch(array, 74) +
            // "个位子。（下标从0计算）");
        }*/
}
